package com.xyj.week03;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class T2 {

    public Map<Integer,Integer> keyToVal;

    public Map<Integer,Integer> keyToFreq;

    public Map<Integer, HashSet<Integer>> freqToKeys;

    public Integer capacity;

    public Integer minFreq;

    public T2(Integer capacity){
        this.keyToVal=new HashMap<>();
        this.keyToFreq=new HashMap<>();
        this.freqToKeys=new HashMap<>();
        this.capacity=capacity;
        this.minFreq=0;
    }

    /**
     * 根据key获取值
     * @param key 键
     * @return V
     */
    public Integer get(Integer key){
        if (!keyToVal.containsKey(key)){
            return -1;
        }
        //key对应的freq+1
        this.increaseFreq(key);
        return keyToVal.get(key);
    }


    public void put(Integer key,Integer value){

        if (keyToVal.containsKey(key)){
            //如果已存在这个key的话,覆盖更新
            keyToVal.put(key,value);
            //key对应的freq+1
            this.increaseFreq(key);
            return;
        }
        //如果这个key不存在的话
        //判断容量是否不足
        if (capacity<=keyToVal.size()){
            //如果容量不足，先删除使用最少的key
            this.removeLastUse();
        }
        //新增一个key,并维护对应的几个map
        keyToVal.put(key, value);
        keyToFreq.put(key,1);
        freqToKeys.putIfAbsent(1,new HashSet<>());
        freqToKeys.get(1).add(key);
        //此时将频率最小值设置为1
        minFreq=1;
    }
    /**
     * 删除这个最少使用的key
     */
    private void removeLastUse() {
        //最少使用的keySet
        HashSet<Integer> keySet = freqToKeys.get(this.minFreq);
        //要删除的key
        Integer deleteKey = keySet.iterator().next();
        //这个key对应的FK map
        keySet.remove(deleteKey);
        if (keySet.isEmpty()){
            //如果keySet中没有其他key了
            freqToKeys.remove(this.minFreq);
        }
        keyToFreq.remove(deleteKey);
        keyToVal.remove(deleteKey);

    }


    /**
     * 维护这个key对应的 KF 和FK集合
     * @param key 键
     */
    private void increaseFreq(Integer key) {
        Integer freq = keyToFreq.get(key);
        //更新KF
        keyToFreq.put(key,freq+1);

        freqToKeys.get(freq).remove(key);
        //维护这个key对应的freq
        freqToKeys.putIfAbsent(freq+1,new HashSet<>());
        freqToKeys.get(freq+1).add(key);

        if (freqToKeys.get(freq).isEmpty()){
            //如果这个freq对应的key为空，清除这个key
            freqToKeys.remove(freq);
            if (freq==this.minFreq){
                this.minFreq++;
            }
        }




    }


}
